/**
 * 题目：1000毒药至多有一瓶有毒，10条狗用于试毒，狗在服药20后会出现中毒症状，
 * 你有24小时得出结论：1.其中有一瓶有毒，得出编号;2.全部都没有毒
 * ***************************************************************
 * 思路：10条狗，狗有中毒和不中毒两种状态，从信息学的角度看，10条狗可以
 * 成为一个具有10位的二进制数。即可以表示1024（0~1023）个编号。将1000个瓶子编成0~999
 * 号。将编号化成2进制表示。然后给对应的2进制上‘1’位置的狗服药。这样，服用
 * 每瓶药的狗位置和数量是不同的，例如编号为2（0000000010）的药只给第二条狗喝。
 * 而14号药（0000001110）只给第2，3，4条狗喝。这样到了最后从中毒的狗的编号和数量
 * 上就可以判断有毒的药是哪一瓶了。当然如果后来没有狗中毒，那就是说没有药是有毒的。
 * 两个结论都可以准确得出。（PS：这是在CSDN上看到的面试题，而思路也受到帖子中
 * 高手的启发）
 */
package charles.testproject.dogandpoison;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

public class DogAndPoison {
	public static void main(String[] args) {
		/**
		 * get a instance of Random for create random number
		 */
		Random r = new Random();
		 /**
		  * create a random number between 0 and 999(inclusive)
		  */
		int randomNumber = r.nextInt(1000);
System.out.println("The randomNumber is: " + randomNumber);
		/**
		 * create a random number between 0 and 1(inclusive), the bottles of
		 * medicine is poisoned or not is depend on it. '0' stands
		 * for 'not' and '1' for the other situation.
		 */
		int isPoisoned = r.nextInt(2);
System.out.println("The vavual of isPoisoned is: " + isPoisoned);
		/**
		 * get a array contains 1000 int numbers modeling 1000 bottles of medicine.
		 * one of them will be poisoned randomly or none of them is. 
		 */
		int [] medicine = new int[1000];
		if(isPoisoned == 1) {
			medicine[randomNumber] = 1;
		}

		//代表10只狗，‘0’代表健康，‘1’代表中毒，初始化时为10只健康的狗
		/**
		 * get a array contains 10 number modeling 10 dogs
		 * they was health when initialing.
		 */
		int [] Dogs = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
		
		for(int j=0; j<1000;j++) {
			String binaryString = Integer.toBinaryString(j);
			int length = binaryString.length();
			int dength = Dogs.length;
			//补齐十位二进制数字符串，在前面加‘0’
			for(int n = 0; n < (Dogs.length - length); n++) {
				binaryString = "0" + binaryString;
			}
			//将字符串转为char类型数组
			//translate the String <binaryString> into a char array.
			char[] cArr = binaryString.toCharArray();
			//给对应瓶子号码的的二进制符上为‘1’的狗喂该瓶药.
			for(int k = cArr.length - 1; k >= 0; k--) {
				if(cArr[k] == '1') {
					Dogs[k] += medicine[j];
				}
			}
		}
		
		//
System.out.println("20 hours later: the situation about the 10 dogs" +
		           "('1'means poisioned ,'0' means not ): ");
System.out.println(Arrays.toString(Dogs));
		int p =1;
		int result = 0;
		for(int h=Dogs.length - 1; h>=0; h--) {
			result += Dogs[h] * p;
			p *= 2;
		}
		if(result!=0) {
			System.out.println("The medicine had been poisoned,the number of the poisoned bottle is: " + result);
		} else {
			System.out.println("The medicine are all clean!");
		}
	}
}
